# coding=utf-8
# Date: 2021/10/1 10:06
from typing import List


# 执行用时：32 ms, 在所有 Python3 提交中击败了77.23%的用户
# 内存消耗：15.2 MB, 在所有 Python3 提交中击败了5.54%的用户
class Solution:
    def destCity(self, paths: List[List[str]]) -> str:
        cnt = {}
        for path in paths:
            a, b = path[0], path[1]
            if a not in cnt:
                cnt[a] = 0
            cnt[a] += 1
            if b not in cnt:
                cnt[b] = 0
        for k, v in cnt.items():
            if v == 0:
                return k
        return ""


if __name__ == "__main__":
    print(Solution().destCity([["London", "New York"], ["New York", "Lima"], ["Lima", "Sao Paulo"]]))
